In the following discussion, we refer to the host computer that originated the request to open a communication channel to the remote host computer as a client, while we refer to the remote host computer which accepted this request from the client as a server. In many reliable data communication protocols, such as TCP, the server controls the timing and rate with which it sends data to the client according to special messages (so-called ACKs) that acknowledge the receipt of previous data packets by the client. The following discussion uses a Web communication sequence carried by HTTP over TCP to illustrate a set of problems common to a wide range of reliable transport protocols.
In order to establish a communication channel to the server, the client first sends a special message to the server requesting it to open a connection. This message is named SYN in TCP. The server confirms its readiness to do that by sending an acknowledgement. This message is called SYN-ACK in TCP. The client then initiates the actual request for data, thereby acknowledging the response from the server. In TCP the actual request for data may be made by transmitting the message HTTPGET from the client; and in some realizations of TCP, two separate packets are transmitted: one containing the ACK for SYN-ACK, and the other one carrying the HTTP GET request. After these steps, the server starts sending packets of data to the client. The rate of sending the data from the server is governed by protocol-specific algorithms (“slow-start” and “congestion avoidance” in the case of TCP) utilizing acknowledgments (ACKs) received by the server for the packets that were successfully received by the client. Since different packets may take different paths from the server to the client, they may arrive in a different order from that in which they were sent. To enable the client to put the packets in proper sequential order, the packets or the data contained within the packets are typically numbered sequentially by the server.
Operating details for the Internet protocol suite are set forth in a series of Requests for Comments (RFC) defined by the Internet Engineering Task Force (IETF). RFC 2581 prescribes that ACKs be generated in TCP for at least every other full-size packet and all out-of-order packets:                “ACK SHOULD be generated for at least every second full-sized packet, and MUST be generated within 500 ms of the arrival of the first unacknowledged packet. Out-of-order data packets SHOULD be acknowledged immediately, in order to accelerate loss recovery. To provide feedback to senders recovering from losses, the receiver SHOULD send an immediate ACK when it receives a data packet that fills in all or part of a gap in the sequence space.”        
If a packet of data, or an ACK for it, is lost then the server is required to retransmit the missing data. Most often retransmission only happens after a certain amount of time specified by the protocol standards following initial transmission of the data. Thus, the entire time out period represents lost transmission time. RFC 3046 describes the time-out problem as follows:                “TCP's retransmission timeout (RTO) is based on measured round-trip times (RTT) between the sender and receiver. To prevent spurious retransmissions of packets that are only delayed and not lost, the minimum RTO is conservatively chosen to be 1 second. Therefore, it behooves TCP senders to detect and recover from as many losses as possible without incurring a lengthy timeout when the connection remains idle.”        
For land-based communication networks typical RTTs are on the order of 100 milliseconds or less. The timeout period typically ranges from 1 to 3 seconds for TCP communications. Thus, the penalty for entering a timeout state is substantial. The goal of the present invention is to reduce the possibility that the client or the server enters this costly timeout state.
Recent implementations of TCP are enhanced by addition of a “fast retransmit” feature. This feature enables a server to avoid timeout by retransmitting a lost packet whenever the server receives acknowledgments from the client, triggered by at least three packets sent after the packet for which an acknowledgement is missing. TCP's fast retransmit system is representative of a broad class of recovery mechanisms which all rely on at least one (in the case of TCP, in fact 3) subsequent packets making it through successfully and triggering acknowledgements after an earlier packet has been lost. However, as RFC 3046 concedes if there are less than three subsequent packets “in flight” after the lost packet; this solution does not work.                “If not enough duplicate ACKs arrive from the receiver, the Fast Retransmit algorithm is never triggered—this situation occurs when the congestion window is small or if a large number of packets in a window are lost. For instance, consider a congestion window (cwnd) of three packets. If one packet is dropped by the network, then at most two duplicate ACKs will arrive at the sender. Since three duplicate ACKs are required to trigger Fast Retransmit, a timeout will be required to resend the dropped packet.”Here, a “duplicate ACK” is an ACK sent by the client repeating acknowledgement of earlier data. In TCP and similar protocols a duplicate ACK is sent by the client when it receives a packet containing other than the next data expected in sequence.        
Unfortunately, with current communication practices, on average less than half of lost packets are eligible for fast retransmit recovery. See Hari Balakrishnan, Venkata Padmanabhan, Srinivasan Seshan, Mark Stemm, and Randy Katz, “TCP Behavior of a Busy Web Server: Analysis and Improvements”, Proc. IEEE INFOCOM Conf. (San Francisco, Calif., March 1998.)
It is noteworthy that the problems cited here are most prominent when: the total amount of data to be sent is small (so that the server has relatively few packets to send); near the end of a transmission (e.g. for the final few packets of a flow); near the start of a transmission (where TCP's “slow-start” feature places additional limits on the number of packets in flight); and when receivers have limited buffer capacity (when their TCP receive “window” is small).